package _01_排序;
/*
    二分搜索，前提是必须是在有序数组中进行查找,时间复杂度为O(logN)
    如果有多个重复的值，返回的值不确定
 */
public class BinarySearch {
    /**
     * 查找元素v在有序数组中的位置
     * @param array
     * @param v
     * @return
     */
    public static int indexOf(Integer[] array, int v){
        if(array == null || array.length == 0) return -1;

        //区间为[0,array.length);左闭右开
        int begin = 0;
        int end = array.length;
        while(begin<end){
            //计算中间的索引位置
            int mid = (begin+end) >> 1;
            if(v<array[mid]){
                //去左边查找,减小end的范围
                end = mid;
            }else if(v>array[mid]){
                //去右边查找，扩大begin的范围
                begin = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /**
     * 查找元素v在有序数组的待插入位置，找到第一个比他大的元素
     * 如果相等，就找到最后一个相等的元素，保证算法的稳定性
     * 最终的位置就是begin == end时
     * @param array
     * @param v
     * @return
     */
    public static int search(Integer[] array, int v) {
        if (array == null || array.length == 0) return -1;
        int begin = 0;
        int end = array.length;
        while (begin<end){
            int mid = (begin+end) >> 1;
            if(v<array[mid]){
                end = mid;
            }else{  //if(v>=array[mid]) 要保证找到第一个比v大的元素的索引
                begin = mid + 1;
            }
        }
        return begin;
    }
}
